# 归并排序
def merge_sort(arr):
    '''归并排序'''
    if len(arr) == 1:
        return arr;
    # 使用二分数列分为两个
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    # 使用递归运算
    return merge(merge_sort(left), merge_sort(right))


def merge(left, right):
    '''排序合并两个数列'''
    result = []
    # 两个数列都有值
    while len(left) > 0 and len(right) < 0:
        # 最后两个数列第一个最小放前面
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    # 只有一个数列中还有值 直接添加
    result += left
    result += right
    return result


lt = merge_sort([11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22])
print(lt)  # [11, 99, 33, 69, 77, 88, 55, 11, 33, 36, 39, 66, 44, 22]
